/*  2 题目标题: 第39级台阶
  3 
  4     小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
  5 
  6     站在台阶前，他突然又想着一个问题：
  7 
  8     如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
  9 
 10 
 11     请你利用计算机的优势，帮助小明寻找答案。(51167078)
 12 
 13 要求提交的是一个整数。
 14 注意：不要提交解答过程，或其它的辅助说明文字。

 * 
 * */
#include <stdio.h>

// 每步1、2个台阶
int mv[] = {1, 2};
int count;

// num台阶数, step步数
void dfs(int num, int step) {
	if(num >= 39) {
		// 满足条件：1、刚好39级，2、右脚做后一步（即走偶数步）
		if(step % 2 == 0 && num == 39)
			count++;
		return ;
	}

	for(int i=0; i<2; i++) {
		dfs(num+mv[i], step+1);
	}
}

int main(void) {
	
	count = 0;
	dfs(0, 0);

	printf("%d\n", count);

	return 0;
}
